The invention relates to a process for the arrangement of equitable-loss packets. Such a process is particularly applicable in a high-volume integrated services network using the ATM (Asynchronous Transfer Mode) technique. In such a network, which is of the packet switching type, the packets have an interacting connection with the packets from other connections at each node at which a switching element would normally be located.
Such networks are designed to allow for communications between applications which call for performance values from the said networks which are becoming constantly more demanding in terms of routing times, jitter (service time variation), packet loss, minimum volume etc.
Traditional packet switching networks are of the type known as best effort; that is to say, they do not provide guarantees of service. The philosophy behind this type of network is that the intelligence is concentrated in the applications, while the network itself is as simple as possible. The result is that, in the event of the network being overloaded, performance values may deteriorate to a substantial degree, which may lead to a significant loss of packets. In addition to this, the joint presence of applications requiring different qualities of service calls for their having a homogeneous type of behavior with regard to congestion, in other words, they are required to obey a rule of reduction in their volume, at the risk of leading to situations in which certain more xe2x80x9caggressivexe2x80x9d applications are accordingly favoured, and take up the larger part of the bandwidth, to the detriment of more conservative applications (those which tend more to obey the behavior rule). There is the risk of this phenomenon becoming all the greater, the greedier the applications become in the bandwidth. It accordingly appears unlikely that several audio and video applications are capable of existing together in harmony.
To resolve these problems, a number of arrangement procedures have been applied which allow for a command to be implemented to determine the order in which the packets deriving from different connections will be served. These procedures are referred to as xe2x80x9cequitablexe2x80x9d, because, when linked to conformity and admission checks, they make it possible to guarantee that a given fraction of the bandwidth of a node is explicitly dedicated to a particular connection. Such a guarantee of volume, extended to all the nodes of a give channel, forms the essential basis for the provision of more sophisticated service guarantees with regard to service time, jitter, or even losses. In a similar way, its relaxation provides the opportunity to improve the use of the network by providing a statistical commitment with regard to the quality of the service supplied.
Accordingly, during the establishment phase of the call, a request relating to the characteristics of the anticipated traffic and performance values is issued. A group of admission check conditions for the connection is tested at each node in the network. The new connection is then accepted by the network if the network resources available are sufficient to satisfy the request for the connection without disturbing existing connections. The network accordingly guarantees that the performance values required will be respected, provided that the subscriber respects the traffic characteristics.
A process for establishing of order is implemented at each node in the network, and consists of determining which packet is to be served for transmission by discriminating between the packets on the basis of the traffic characteristics of their performance requests.
A first establishing of order process known under the service name of xe2x80x9cFirst In, First Out xe2x80x9d (FIFO) makes use of a queue for each output link of a network node, in which the incoming flows are multiplexed.
In the context of the FIFO process used in the traditional manner, Demers et al and Parekh and Gallager have jointly proposed another process known as Generalised Processor Sharing Discipline, or GPS discipline. Descriptions of this process have been given, on the one hand, in the article which appeared in the Journal of Internet Working Research and Experiment, October 1990, pages 3 to 26, and entitled xe2x80x9cAnalysis and simulation of a fair queuing algorithmxe2x80x9d, and, on the other, in another article which appeared in the journal Proceedings of IEEE of Infocom, pages 914 to 924, 1992, entitled xe2x80x9cA Generalized Processor Sharing Approach to Flow Control in Integrated Service Networks - The Single Node Casexe2x80x9d. The basic principle of this process is summarised hereinafter.
Given a collection of weightings r1. . . rN associated with the flows 1, . . . N. A node implements the GPS discipline, being given two instants s and t, if the quantities of data Wi(s,t) and Wj(s,t) serving for two flows i and j active between s and t are such that:                                                         W              i                        ⁡                          (                              s                ,                t                            )                                                          W              j                        ⁡                          (                              s                ,                t                            )                                      =                              r            i                                r            j                                              (        1        )            
A flow is active between s and t is at least one packet o the said flow is present in the queue or is in the course of service between the instants s and t.
The weightings r1 to rN are directly proportional to the quantities allocated respectively to the connections 1 to N. Such an establishing of order process may also be considered as equitable in the sense that it allows for the division of the output capacity in precise proportion to the weightings and therefore of the quantities allocated to the different flows.
It is likewise considered that the relationship indicated above defines a fluid model. In fact, if the hypothesis of fluid flow is adopted, it is possible to serve traffic units as small as may be desired, or, likewise, to serve all the flows in parallel. As a result, it is possible to divide the service into precise proportions of the weightings of the flows, at any time. Nevertheless, the problem posed by a fluid model is that of its implementation in the context of flows consisting of packets.
Equation (1) may be rewritten in the form:                     W        i            ⁢              (                  s          ,          t                )                    r      i        =                              W          j                ⁢                  (                      s            ,            t                    )                            r        j              =          q      ⁢              (                  s          ,          t                )            
The quantity q(s,t) is referred to as the normalised quantity. For a flow k, this quantity is generally annotated.
            w      k        ⁢          (              s        ,        t            )        =                              W          k                ⁢                  (                      s            ,            t                    )                            r        k              .  
This can be written as q(s,t)=v(t)-v(s)
The function v(t) represents the development over time of the function q(s,t), and is known as the virtual time function of the system. The virtual time defined in this manner increases in step with the growth of service in the system. It can be shown that v(t) is an incrementing string function, linear in the form of fragments, of which the slope at any moment t is inversely proportional to the sum of the weighting of the flows which are then active.
In current networks, one single flow is served at a given moment, and this service corresponds to the transmission, which cannot be pre-emptied, of a data packet of variable size. As a result of this, it is necessary to approximate the fluid model described above by a mechanism which manipulates the final entities such as the packets, while still approaching as closely as possible to the xe2x80x9cidealxe2x80x9d equability of the fluid model. The general principle of known forms of implementation, referred to as fair queuing, and known without distinction as PGPS (Packetized Generalized Processor Sharing) or WFQ (Weighted Fair Queuing) is based on the marking of the packets entering with the aid of the virtual time function of the server, and their insertion in a queue which is selected on the basis of the incrementing markings. The packet selected for transmission is then the first packet in the queue.
The objective of the invention differs from that of the fluid model described above. It is in fact possible to distinguish between three types of guarantees which must be offered to the user of an adaptive application. The first guarantee relates to the volume. In fact, for the adaptation threshold reasons indicated earlier, it is essential to supply a minimum volume limit which is reserved for the flow under consideration. This minimum volume will allow, for example, for the baseband to be served with a hierarchical flow, or will be transformed into a guaranteed maximum loss rate in the case of a redundant flow.
The second guarantee relates to the service time. We shall consider below the service time of a packet, which breaks down into a waiting period in the queue and a transmission time on the link, the propagation times and the jitter not being considered. In fact, whether the application obeys an interactivity constraint or not, the receiver(s) must be provided with a reception queue, referred to technically as the xe2x80x9cplayout bufferxe2x80x9d, the length of which is determined by the maximum service time which the receivers(s) can achieve. It will be noted that this maximum guaranteed service time relates to all the flow packets, and not to the minimum quantity reserved.
The third guarantee is of a different nature; a user can in fact legitimately demand that his flow should only be subject to degrading if the flows from other users are equally degraded, and in the same proportions. This accordingly constitutes a guarantee which relates to the equability of distribution of resources in the network, a corollary to the homogeneous behavior on the best-effort network, as outlined earlier. In this case, it is the network which undertakes to supply an equitable service, irrespective of the behaviour of the applications, which consequently are not obliged to co-operate.
The objective of the invention is to provide a process which will allow for these three guarantees to be offered. The task is, therefore, to define simultaneously an equability of distribution of the bandwidth which will meet the needs of the adaptive flows, and a fluid model, capable of being approximated by a mechanism which manipulates the packets.
To achieve this, a process of establishing of order of packets according to the invention is of this type which consists of serving, on the output link of a network node, the packets which derive from a multiplicity of input packet flows, a minimum quantity ri being reserved for each input flow, and a quantity xi(t) being allocated to each time f for each input flow. It is characterised in that the packets are served in such a way that, at all times, the ratio between the part xcex1xi(t) to the allocated quantity xi(t) is above the minimum reserved quantity ri on the part ei(t) of the instantaneous quantity xcexi(t), with the minimum reserve quantity ri adopting the same value K(t) at this time for all the flows which are active.
This invention likewise relates to systems provided for the implementation of a process for establishing order according to the invention.